The present invention relates to processing data, and more particularly to processing multidimensional data.
Many multidimensional data processing algorithms are based on multiresolution decompositions. These algorithms include, for example, compression algorithms, noise removal algorithms, and algorithms for the reconstruction of images. The more efficiently these algorithms operate, the better the modern communications and information processing systems in which they are embedded operate. For example, efficient compression algorithms permit fast transmission of information in communication systems. Without efficient compression algorithms, multidimensional data requires an unacceptable amount of bandwidth for transmission and an unacceptable amount of storage for archiving.
Consider, for example, a medical image, such as a mammographic screening image, which may be represented by four six-thousand pixel by six-thousand pixel arrays. A mammographic screening image consists of four images, two images for each of two breasts. Of the two images associated with each breast, one image is a top image and one image is a side image. A pixel is a xe2x80x9cpicture element,xe2x80x9d which is an elementary unit of information contained in an image and is typically represented by an intensity level. If each pixel in the mammographic screening image is represented by sixteen bits, then each pixel may be encoded at one of 65,536 possible intensity levels. To transmit the mammographic screening image without compression, 2.3 billion bits must be sent over a communication link. A typical telephone line is capable of transmitting about 56,000 bits per second, so transmission of a mammographic screening image would require more than ten hours. A ten hour transmission time is unacceptable for transmitting a mammographic screening image, so image compression processing is used to reduce the transmission time.
Prior to processing multidimensional data using some compression methods, such as wavelet compression, the multidimensional data is approximated at several resolution levels. For example, two-dimensional image data is initially divided into two rows and two columns. Each row and each column is subsequently divided into two rows and two columns. FIG. 1 is an illustration of a sequence of images 100, including images 101, 103, 105, and 107, of multidimensional data partitioned into rows and columns. The images 101, 103, 105, and 107 illustrate partitioning a first dimensions 109 (rows) and a second dimension 111 (columns) at a rate of one. Image 101 is partitioned in the first dimension 109 and the second dimension 111. Each of the partitions in image 101 is partitioned or divided to form image 103. Each of the partitions in image 103 are partitioned or divided to form image 105. And each of the partitions in image 105 are partitioned or divided to form image 107. The partitioning or subdividing of rows and columns continues until an acceptable resolution level is achieved. An acceptable resolution level is a level at which data can be compressed, transmitted, and decompressed, such that the decompressed data includes the information contained in the original data required by a viewer of the received data. For example, in the mammographic screening example described above, the decompressed data must contain enough information related to a cancerous tumor to allow a radiologist to identify the cancerous tumor by viewing the mammographic screening images reconstructed from the compressed data.
Isotropic decomposition is one type of decomposition used in some multidimensional data processing algorithms. To perform isotropic decomposition, one begins with a function xcfx86 of one variable such that the set
{xcfx86(xxe2x88x92j)|jxcex5}
forms a Riesz basis for the span of these functions. Assume that xcfx86 satisfies the rewrite rule                               φ          ⁡                      (            x            )                          =                              ∑            j                    ⁢                                    a              j                        ⁢                          φ              ⁡                              (                                  x                  -                  j                                )                                                                        (        1        )            
for a finite set of coefficients xcex1j. Let Sk be the space of all functions             S      k        :=                            {                                    ∑              j                        ⁢                                          c                j                            ⁢                              φ                ⁡                                  (                                                                                    2                        k                                            ⁢                      x                                        -                    j                                    )                                                              "RightBracketingBar"                ⁢                  c          j                    ∈      ℝ        }
and choose a bounded projection Pk from Lp () to Sk. Under certain conditions (see Daubechies) any ƒxcex5Lp() can be re-written as   f  =                    lim                  k          ->          ∞                    ⁢              P        k              =                            P          0                ⁢        f            +                        ∑                      k            =            1                    ∞                ⁢                  (                                                    P                k                            ⁢              f                        -                                          P                                  k                  -                  1                                            ⁢              f                                )                    
where, because of the rewrite rule (1), Pkƒxe2x88x92Pkxe2x88x921ƒ is in Sk. Thus, since P0ƒxcex5S0,                     f        =                ⁢                                            P              0                        ⁢            f                    +                                    ∑                              k                =                1                            ∞                        ⁢                          (                                                                    P                    k                                    ⁢                  f                                -                                                      P                                          k                      -                      1                                                        ⁢                  f                                            )                                                              =                ⁢                                            ∑                              j                ∈                Z                                      ⁢                                          d                j                            ⁢                              φ                ⁡                                  (                                      ·                                          -                      j                                                        )                                                              +                                    ∑                              k                =                1                            ∞                        ⁢                                          ∑                                  j                  ∈                  Z                                            ⁢                                                d                                      j                    ,                    k                                                  ⁢                                                      φ                    ⁡                                          (                                                                        2                          k                                                ·                                                  -                          j                                                                    )                                                        .                                                                        
For suitable functions xcfx86 and special projectors Pk, one can find a function "psgr", associated with xcfx86, such that                     P        k            ⁢      f        -                  P                  k          -          1                    ⁢      f        =            ∑              j        ∈        Z              ⁢                  c                  j          ,                      k            -            1                              ⁢              ψ        ⁡                  (                                    2                              k                -                1                                      ·                          -              j                                )                    
(note the new scaling xe2x88x922kxe2x88x921 instead of 2k) so that   f  =                    ∑                  j          ∈          Z                    ⁢                        d          j                ⁢                  φ          ⁡                      (                          ·                              -                j                                      )                                +                  ∑                  k          =          0                ∞            ⁢                        ∑                      j            ∈            Z                          ⁢                              c                          j              ,              k                                ⁢                                    ψ              ⁡                              (                                                      2                    k                                    ·                                      -                    j                                                  )                                      .                              
For a function ƒ: xe2x86x92 a similar decomposition holds. Define a set xcexa8 of 2dxe2x88x921 functions defined for x=(x1, . . . , xd)xcex5 by   Ψ  :=      {                  ∏                  i          =          1                d            ⁢              xe2x80x83            ⁢                                    v            i                    ⁡                      (                          x              i                        )                          ⁢                              "LeftBracketingBar"                                          v                i                            =                                                φ                  ⁢                                      xe2x80x83                                    ⁢                  or                  ⁢                                      xe2x80x83                                    ⁢                                      v                    i                                                  =                ψ                                      }                    ⁢          \          ⁢                      {                                          ∏                                  i                  =                  1                                d                            ⁢                              xe2x80x83                            ⁢                              φ                ⁡                                  (                                      x                    i                                    )                                                      }                              
together with the function       Φ    ⁡          (      x      )        =            ∏              i        =        1            d        ⁢          xe2x80x83        ⁢                  φ        ⁡                  (                      x            i                    )                    .      
Then, under suitable conditions, any ƒ in Lp() can be written as   f  =                    ∑                  j          ∈                      Z            d                              ⁢                        d          j                ⁢                  Φ          ⁡                      (                          ·                              -                j                                      )                                +                  ∑                  k          =          0                ∞            ⁢                        ∑                      j            ∈                          Z              d                                      ⁢                              ∑                          ψ              ∈              Ψ                                ⁢                                    c                              j                ,                k                                      ⁢                                          ψ                ⁡                                  (                                                            2                      k                                        ·                                          -                      j                                                        )                                            .                                          
Note that, since x=(x1, . . . , xd) and the multi-index j=(j1, . . . , jd),
"psgr"(2kxxe2x88x92j)="psgr"(2kx1xe2x88x92j1, . . . , 2kxdxe2x88x92jd),
i.e., each of the components xi of x has been scaled by the same amount, 2k.
One disadvantage of isotropic decomposition is that not all data is isotropic, and anisotropic multidimensional data is not efficiently processed by algorithms based on isotropic decomposition.
For these and other reasons there is a need for the present invention.
According to one aspect of the present invention, a method is described for forming multi-resolution representations of data. The method includes the operations of partitioning the data in a first dimension at a first rate, and partitioning the data in a second dimension at a second rate, wherein the first rate is not equal to the second rate.